package com.leetcode.algorithm.y22.m06;

/**
 * 45. 跳跃游戏 II
 * 
 * https://leetcode.cn/problems/jump-game-ii/
 * 
 * @author jie.deng
 *
 */
class Question0045Solution03 {

	// 贪心算法
	public int jump(int[] nums) {
		// 关键点：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点。
		// 前提条件：
		// 局部最优：求当前这步的最大覆盖，那么尽可能多走，到达覆盖范围的终点，只需要一步。
		// 全局最优：达到终点，步数最少。
		int len = nums.length;
		if (len == 1) {
			return 0;
		}
		int step = 1;
		// 第0步最远可达的下标
		int prevMaxIdx = 0;
		// 第1步最远可达的下标
		int maxIdx = nums[0];

		while (maxIdx < len - 1) {
			// 第step可以到达的节点是[prevMaxIdx+1, maxIdx]
			// 状态初始化
			int i = prevMaxIdx + 1;
			int j = maxIdx;
			prevMaxIdx = maxIdx;
			step++;
			for (; i < len && i <= j; i++) {
				// 当前步最远可达的节点
				maxIdx = Math.max(maxIdx, i + nums[i]);
			}
		}

		return step;
	}

}